import numpy as np
import matplotlib.pyplot as plt

# 城市坐标列表
coordinates = [
    (1304, 2312), (3639, 1315), (4177, 2244), (3712, 1399), (3488, 1535),
    (3326, 1556), (3238, 1229), (4196, 1004), (4312, 790), (4386, 570),
    (3007, 1970), (2562, 1756), (2788, 1491), (2381, 1676), (1332, 695),
    (3715, 1678), (3918, 2179), (4061, 2370), (3780, 2212), (3676, 2578),
    (4029, 2838), (4263, 2931), (3429, 1908), (3507, 2367), (3394, 2643),
    (3439, 3201), (2935, 3240), (3140, 3550), (2545, 2357), (2778, 2826),
    (2370, 2975)
]

# 计算距离矩阵
num_cities = len(coordinates)
distance_matrix = np.zeros((num_cities, num_cities))
for i in range(num_cities):
    for j in range(num_cities):
        if i != j:
            distance_matrix[i][j] = np.linalg.norm(np.array(coordinates[i]) - np.array(coordinates[j]))

# 蚁群算法参数设置
num_ants = num_cities
num_iterations = 500
alpha = 1.0    # 信息素重要性因子
beta = 2.0     # 启发因子重要性因子
evaporation_rate = 0.5  # 信息素挥发系数
Q = 100        # 信息素增加强度

# 初始化信息素矩阵
pheromone_matrix = np.ones((num_cities, num_cities))

# 路径选择函数
def select_next_city(allowed, current_city, pheromone, distance):
    probs = []
    for city in allowed:
        tau = pheromone[current_city][city] ** alpha
        eta = (1 / distance[current_city][city]) ** beta
        probs.append(tau * eta)
    probs /= np.sum(probs)
    return np.random.choice(allowed, p=probs)

# 蚂蚁算法主循环
best_distance = float('inf')
best_path = []

for iteration in range(num_iterations):
    all_paths = []
    all_distances = []

    for ant in range(num_ants):
        path = []
        visited = set()
        current_city = np.random.randint(num_cities)
        path.append(current_city)
        visited.add(current_city)

        for _ in range(num_cities - 1):
            allowed = [city for city in range(num_cities) if city not in visited]
            next_city = select_next_city(allowed, current_city, pheromone_matrix, distance_matrix)
            path.append(next_city)
            visited.add(next_city)
            current_city = next_city

        path_distance = sum(distance_matrix[path[i], path[i + 1]] for i in range(-1, num_cities - 1))
        all_paths.append(path)
        all_distances.append(path_distance)

        if path_distance < best_distance:
            best_distance = path_distance
            best_path = path

    # 更新信息素矩阵
    pheromone_matrix *= (1 - evaporation_rate)
    for i, path in enumerate(all_paths):
        for j in range(-1, num_cities - 1):
            pheromone_matrix[path[j], path[j + 1]] += Q / all_distances[i]

# 输出结果
print("最短路径距离:", best_distance)
print("最优路径:", best_path)

# 可视化最优路径
x = [coordinates[city][0] for city in best_path]
y = [coordinates[city][1] for city in best_path]
plt.plot(x, y, marker='o', color='b')
plt.title("Best Path Found by Ant Colony Optimization")
plt.xlabel("X Coordinate")
plt.ylabel("Y Coordinate")
plt.show()